Кратко обозначим структуру лекции. Пройдём от базовых понятий до современных алгоритмов планирования, включая многопроцессорные системы и системы реального времени.
Планирование — ключевая функция ОС. Без неё процессы не смогли бы совместно использовать процессор. Разберём, как ОС решает, кому и на сколько отдавать процессорное время.
Три ключевых аспекта планирования: какой процесс выбрать, как долго он работает и как переключить контекст. Это фундамент для всех последующих алгоритмов.
Две главные группы целей — производительность и отзывчивость. Для пакетных систем важнее throughput, для интерактивных — время отклика.
Справедливость и эффективность ресурсов — ещё два критерия. Обратите внимание на предотвращение голодания: это ключевая проблема многих алгоритмов.
Переходим к уровням планирования. Долгосрочное работает редко — секунды и минуты. Его главная задача — контроль степени мультипрограммирования.
Среднесрочное планирование отвечает за swapping — обмен процессами между памятью и диском. Критически важно для предотвращения трэшинга.
Краткосрочное планирование — самый частый уровень, работает каждую миллисекунду. Именно здесь алгоритмы показывают свою эффективность.
Превентивные алгоритмы принудительно прерывают процесс — лучшая отзывчивость, но нужен таймер. Непревентивные проще, но возможна монополизация процессора.
Разделение по доступности информации о времени выполнения. Алгоритмы без этой информации проще, с ней — потенциально эффективнее.
Многоочередные системы позволяют разделять процессы по категориям и применять разные стратегии. Это основа для MLQ и MLFQ, которые рассмотрим далее.
Простейший алгоритм — как очередь в магазине. Главный минус — эффект конвоя: короткий процесс может долго ждать за одним длинным.
SJF даёт математически оптимальное среднее время ожидания. Проблема: время выполнения обычно неизвестно — его оценивают по прошлому поведению процесса.
Round Robin — самый распространённый алгоритм для интерактивных систем. Ключевой параметр — размер кванта: слишком малый даёт накладные расходы, слишком большой — плохую отзывчивость.
Приоритетное планирование гибко, но создаёт проблему голодания. Решение — старение приоритетов: чем дольше ждёт процесс, тем выше его приоритет.
Многоуровневая очередь — статическое разделение. Системные процессы наверху, пакетные внизу. Процессы не мигрируют — это и ограничение, и простота.
MLFQ — один из самых практичных алгоритмов. Он автоматически определяет тип процесса по поведению и не требует априорной информации о задачах.
Этот подход гарантирует каждому процессу определённую долю CPU. Особенно важен в мультимедийных системах и системах реального времени, где предсказуемость критична.
Fair Share учитывает не только процессы, но и пользователей. Без него один пользователь может запустить десятки процессов и монополизировать процессор.
Переходим к многопроцессорным системам. Главная сложность — не только выбрать задачу, но и выбрать правильный процессор, учитывая локальность данных и кэши.
Аффинность пытается удержать процесс на том же ядре для использования кэша. Мягкая — рекомендация, жёсткая — строгое ограничение, важное в real-time системах.
Push и pull миграции — два подхода к балансировке. В современных ОС обычно используется комбинация обоих для оптимального распределения нагрузки между ядрами.
В системах реального времени сроки выполнения — не пожелание, а требование. Нарушение дедлайна в hard real-time ведёт к катастрофическим последствиям.
RMS назначает приоритеты по частоте — просто и эффективно. EDF более гибок, но сложнее в реализации. LLF учитывает запас времени до дедлайна.
Перед запуском real-time системы нужно доказать, что все дедлайны будут соблюдены. Используются формулы достаточного условия и симуляция.
Потоки легче процессов — переключение быстрее, ресурсы разделяются. Но добавляется сложность: кто планирует — ядро или пользовательская библиотека?
Пользовательские потоки быстрые, но без истинного параллелизма. Ядерные дают параллелизм, но дороже. Гибридные модели пытаются совместить лучшее из обоих миров.
Для сравнения алгоритмов нужны метрики — количественные и качественные. Нет идеального алгоритма, есть оптимальный для конкретной задачи.
Аналитические методы дают теоретические оценки, экспериментальные — практические. Хороший анализ использует оба подхода и подкрепляется инструментами мониторинга.
Каждый алгоритм имеет компромиссы. FCFS прост, но несправедлив; RR отзывчив, но с накладными расходами; MLFQ адаптивен, но сложен в реализации.
Современный тренд — «зелёные» алгоритмы. DVFS снижает частоту процессора для экономии энергии. Консолидация задач уменьшает число активных ядер.
В облаках планировщик управляет тысячами виртуальных машин и контейнеров. Serverless — новый уровень абстракции, где планирование скрыто от разработчика.
ML позволяет автоматически настраивать параметры планировщика под конкретную нагрузку. Вместо статических эвристик — адаптивные модели, обучающиеся на поведении процессов.
Квантовые и нейроморфные вычисления потребуют принципиально новых подходов к планированию. Этические аспекты тоже важны — ИИ-планировщики должны быть прозрачными.
Подведём итоги. Четыре фундаментальных принципа: балансировка, адаптивность, эффективность и справедливость. Выбор алгоритма всегда зависит от контекста.
Главные тезисы лекции в концентрированном виде. Рекомендую запомнить ключевые алгоритмы и их компромиссы — это основа для экзамена.
Используйте эти вопросы для проверки понимания материала. Если можете ответить на все десять — тема усвоена хорошо.
Для углублённого изучения рекомендую Таненбаума и OSTEP. Документация Linux CFS — отличный пример реального планировщика в production.